#include <stdio.h>

/******************************************/
/* 思路： 每次寻找除底层外最大的饼，
/* 先将其反转到最上层，然后再按顺序反转到下层
/******************************************/


/******************************************/
/* 翻转
/******************************************/
int evertint(int* arr, int l, int r, int* count)
{
	int i,j,tmp;
	i = l;
	j = r;

	while (j>i)
	{
		tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;

		i ++;
		j --;

		*count = *count + 1;
	}
}

/******************************************/
/* 将未排序的最大饼反转到底层
/* @parameter 
/*     arr: 待排序饼序列(链表头)
/* @return
/*     0: 反转完成
/*     1: 反转失败
/******************************************/
int bigsort01(int* arr, int tail, int* count)
{
	int i;
	int imax;
	int tmp;

	imax = 0;
	for(i=0;i<=tail;i++)
	{
		if (arr[imax] < arr[i])
		{
			imax = i;
		}
	}

	// 不需移动
	if (imax == tail)
	{
		return (tail-1);
	}

	// 该饼翻转到最上
	evertint(arr, 0, imax, count);

	// 该饼翻转到其正确位置
	evertint(arr, 0, tail, count);

	return (tail-1);
}

/******************************************/
/* 判断是否已完成排序
/* @parameter 
/*     arr: 待排序饼序列
/*     length: 序列长度
/* @return
/*     0: 完成
/*     1: 未完成
/******************************************/
int checksort(int* arr, int length)
{
	int i;

	return (0);
}

/******************************************/
/* bigsort
/* 每次找最大饼并反转到底层
/* @return
/*     >0: 完成 翻转次数
/*     -1: 失败
/******************************************/
int bigsort(int* arr, int length)
{
	int s;
	int count;

	count = 0;
	s = length;

	while (s>0)
	{
		s = bigsort01(arr,s,&count);
	}

	return (count);
}

/******************************************/
/* main
/******************************************/
#define LENGTH 5
void main()
{
	int i;
	int count;
	int cake[LENGTH];

	// 饼尺寸赋值
	cake[0] = 2;
	cake[1] = 4;
	cake[2] = 3;
	cake[3] = 1;
	cake[4] = 5;

	count = bigsort(cake, LENGTH-1);

	for (i=0;i<LENGTH;i++)
	{
		printf("%d\r\n", cake[i]);
	}

	printf( "count: %d\r\n", count);
}